// Implementing KMP Search Algorithm to search all the instances of pattern in
// given text
// Reference Book: Introduction to Algorithms, CLRS

// Explanation: https://www.topcoder.com/community/competitive-programming/tutorials/introduction-to-string-searching-algorithms/

const computeLPS = ( pattern ) => {
  const lps = Array( pattern.length )
  lps[ 0 ] = 0
  for ( let i = 1; i < pattern.length; i++ ) {
    let matched = lps[ i - 1 ]
    while ( matched > 0 && pattern[ i ] !== pattern[ matched ] ) {
      matched = lps[ matched - 1 ]
    }
    if ( pattern[ i ] === pattern[ matched ] ) {
      matched++
    }
    lps[ i ] = matched
  }
  return lps
}

/**
 * Returns all indices where pattern starts in text
 * @param {*} text a big text in which pattern string is to find
 * @param {*} pattern the string to find
 */
const KMPSearch = ( text, pattern ) => {
  if ( !pattern || !text ) {
    return [] // no results
  }

  // lps[i] = length of proper prefix of pattern[0]...pattern[i-1]
  //          which is also proper suffix of it
  const lps = computeLPS( pattern )
  const result = []

  let matched = 0
  for ( let i = 0; i < text.length; i++ ) {
    while ( matched > 0 && text[ i ] !== pattern[ matched ] ) {
      matched = lps[ matched - 1 ]
    }
    if ( text[ i ] === pattern[ matched ] ) {
      matched++
    }
    if ( matched === pattern.length ) {
      result.push( i - pattern.length + 1 )
      matched = lps[ matched - 1 ]
    }
  }

  return result
}

export {
  KMPSearch
}
